package com.huangkailong.leetcode;

/**
 * 给你一个字符串s和一个字符规律p，请你来实现一个支持 '.'和'*'的正则表达式匹配。<br/>
 * <br/>
 * '.' 匹配任意单个字符<br/>
 * '*' 匹配零个或多个前面的那一个元素<br/>
 * 所谓匹配，是要涵盖整个字符串s的，而不是部分字符串。<br/>
 * <br/>
 * <br/>
 * 示例 1：<br/>
 * <br/>
 * 输入：s = "aa" p = "a"<br/>
 * 输出：false<br/>
 * 解释："a" 无法匹配 "aa" 整个字符串。<br/>
 * 示例 2:<br/>
 * <br/>
 * 输入：s = "aa" p = "a*"<br/>
 * 输出：true<br/>
 * 解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。<br/>
 * 示例3：<br/>
 * <br/>
 * 输入：s = "ab" p = ".*"<br/>
 * 输出：true<br/>
 * 解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。<br/>
 * 示例 4：<br/>
 * <br/>
 * 输入：s = "aab" p = "c*a*b"<br/>
 * 输出：true<br/>
 * 解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。<br/>
 * 示例 5：<br/>
 * <br/>
 * 输入：s = "mississippi" p = "mis*is*p*."<br/>
 * 输出：false<br/>
 * <br/>
 * <br/>
 * 提示：<br/>
 * <br/>
 * 0 <= s.length<= 20<br/>
 * 0 <= p.length<= 30<br/>
 * s可能为空，且只包含从a-z的小写字母。<br/>
 * p可能为空，且只包含从a-z的小写字母，以及字符.和*。<br/>
 * 保证每次出现字符* 时，前面都匹配到有效的字符<br/>
 * <br/>
 * @author huangkl
 * @since 1.0.0
 */
public class RegxMatch {

    /**
     * TODO 没弄懂的问题 状态方程的推导
     *
     * 动态规划
     */
    public static boolean solution1(String s, String p) {
        int sLen = s.length();
        int pLen = p.length();

        // 数组默认全部初始化为 false
        boolean[][] dp = new boolean[sLen+1][pLen+1];
        // 空字符串默认匹配
        dp[0][0] = true;
        // i 表示的 s 下标，从空串开始，空串与任何模式都匹配
        // j 表示的 p 的下标，从第 1 个字符开始
        for (int i = 0; i <= sLen; i++) {
            for (int j = 1; j <= pLen; j++) {
                // 字符从 0 开始，所以 p 第 j 个字符，其下标为 j-1
                if(p.charAt(j-1) == '*'){
                    // 默认匹配 0 次
                    dp[i][j] = dp[i][j-2];
                    if(matches(s, i, p, j-1)){
                        dp[i][j] = dp[i][j] || dp[i-1][j];
                    }
                }else {
                    if(matches(s, i, p, j)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }
            }
        }

        return dp[sLen][pLen];
    }

    /**
     *
     * @param s s 被匹配的字符串
     * @param i s 第 i 个字符的坐标
     * @param p 匹配模式
     * @param j s 第 j 个字符的坐标
     * @return true 匹配， false 不匹配
     */
    private static boolean matches(String s, int i, String p, int j){
        if(i == 0){
            // i 最小为 1
            return false;
        }
        // s 第 i 个字符，其字符下标为 i - 1
        char s1 = s.charAt(i - 1);
        // p 第 j 个字符，其字符下标为 j - 1
        char p1 = p.charAt(j - 1);

        return p1 == '.' || s1 == p1;
    }
}
